package com.yt.ds.chapter4;

import java.util.Stack;

/**
 * @Author: lzf
 * @Date: 2020/7/30 10:25
 * @Description: 有向环
 */
public class DirectedCycle implements Cycle {
    private boolean[] marked;   // 是否访问过
    private int[] edgeTo;
    private Stack<Integer> cycle;
    private boolean[] onStack;

    public DirectedCycle(Graph graph) {
        onStack = new boolean[graph.getVertexNum()];
        edgeTo = new int[graph.getVertexNum()];
        marked = new boolean[graph.getVertexNum()];
        for (int v = 0; v < graph.getVertexNum(); v++) {
            if (!marked[v]) {
                dfs(graph, v);
            }
        }
    }

    /**
     * 描述：深度优先搜索  1.将访问的点设置为以访问  2.递归访问所有没有被标记过的邻居顶点
     *
     * @param graph 图
     * @param v     顶点
     * @return "void"
     * @date: 2020/7/27 17:45
     */
    private void dfs(Graph graph, int v) {
        marked[v] = true;
        onStack[v] = true;
        // 不是很懂这段代码，stack起到什么作用
        for (int w : graph.adj(v)) {
            if (hasCycle()) {
                return;
            } else if (!marked[w]) {
                edgeTo[w] = v;
                dfs(graph, w);
            } else if (onStack[w]) {
                cycle = new Stack<>();
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
    }

    @Override
    public boolean hasCycle() {
        return cycle != null;
    }

    public Iterable<Integer> cycle() {
        return cycle;
    }
}
